An audience measurement system typically includes one or more device meters to monitor the media presented by one or more media devices located at one or more monitored sites. Such a device meter can use watermarks decoded from the presented media or signatures (also referred to as media fingerprints) generated from the presented media, or both, to monitor (e.g., identify and track) the media being presented by a media device. When signatures are used for media monitoring, signatures of the monitored media (referred to herein as collected signatures or monitored signatures) are generated by the device meter and compared to reference signatures representative of reference media known to the audience measurement system. For media monitoring applications in which the amount of reference media for comparison is large, correspondingly large signatures (e.g., having high resolution) are usually needed to accurately identify the monitored media within a reasonable time period.